/*
提交链接：https://leetcode.cn/problems/find-all-good-strings/submissions/572342345
1397. 找到所有好字符串-困难
完成日期：2024/10/13
数位DP
*/

class Solution {
public:
    const int MOD = 1e9 + 7;
    vector<int> buildKMPTable(const string& evil) {
        int m = evil.size();
        vector<int> lps(m, 0);
        for (int i = 1, j = 0; i < m; ++i) {
            while (j > 0 && evil[i] != evil[j]) {
                j = lps[j - 1];
            }
            if (evil[i] == evil[j]) {
                j++;
            }
            lps[i] = j;
        }
        return lps;
    }
    int dfs(int pos, bool isPrefixS1, bool isPrefixS2, int evilLen, string& s1, string& s2, const string& evil,
             vector<vector<vector<vector<int>>>>& dp, const vector<int>& lps) {
        if (evilLen == evil.size()) return 0; // 包含 evil
        if (pos == s1.size()) return 1; // 完成构造
        if (dp[pos][isPrefixS1][isPrefixS2][evilLen] != -1) return dp[pos][isPrefixS1][isPrefixS2][evilLen];
        char lower_bound = isPrefixS1 ? s1[pos] : 'a';
        char upper_bound = isPrefixS2 ? s2[pos] : 'z';
        long long count = 0;
        for (char ch = lower_bound; ch <= upper_bound; ++ch) {
            bool newIsPrefixS1 = isPrefixS1 && (ch == s1[pos]);
            bool newIsPrefixS2 = isPrefixS2 && (ch == s2[pos]);
            // KMP更新
            int newEvilLen = evilLen;
            while (newEvilLen > 0 && evil[newEvilLen] != ch) {
                newEvilLen = lps[newEvilLen - 1];
            }
            if (evil[newEvilLen] == ch) {
                newEvilLen++;
            }
            count = (count + dfs(pos + 1, newIsPrefixS1, newIsPrefixS2, newEvilLen, s1, s2, evil, dp, lps)) % MOD;
        }
        return dp[pos][isPrefixS1][isPrefixS2][evilLen] = count;
    }
    int findGoodStrings(int n, string s1, string s2, string evil) {
        vector<vector<vector<vector<int>>>> dp(n + 1, vector<vector<vector<int>>>(2, vector<vector<int>>(2, vector<int>(evil.size(), -1))));
        vector<int> lps = buildKMPTable(evil);
        return dfs(0, true, true, 0, s1, s2, evil, dp, lps);
    }
};